Worksheet 6, Math 151

NEWTON'S METHOD

Introduction

Goals : The student will become familiar with Newton's method for attaining successive approximations to the zero of a function. The  While / Do  and the  For / Do statements and the Print command will be utilized in this worksheet. The successive approximations will also be illustrated graphically.

Newton's method  is a technique utilized to approximate the zeros of a function. It is based on the observation that, in most cases, if we make a fairly good initial guess, say (Subscript[x, 0]), to the zero of a function, f, then the x-intercept of the tangent line to the graph of f at ((Subscript[x, 0]),f ((Subscript[x, 0]))) called (Subscript[x, 1]), is a better estimate of the zero than was (Subscript[x, 0]). Repeating this process n times, we find that the (n + 1)st approximation is given by:
(Subscript[x, n+1])=(Subscript[x, n])-((f((Subscript[x, n])))/(f'((Subscript[x, n])))).

Examples

Example 1

Find all numbers x in the interval  [0,1]  for which   (([cos(((3 π x)/2))] )^2)=x.
To determine the number of solutions to this problem, we plot a graph of the functions
F(x)=(([cos(((3 π x)/2))] )^2) and G(x)=x for 0<x<1. 
Then the solutions to this problem are all the values of x at which F(x)=G(x) .

funcF[x_]:=(Cos[3*Pi*x/2])^2
funcG[x_]:=x

It is also evident that the solutions to our problem are the zeros of the function
                                              f(x)=G(x)-F(x).
We plot a graph of the functions f, F, and G to illustrate our remark.

f[x_]:=funcG[x]-funcF[x]
Plot[{funcF[x], funcG[x], f[x]},{x,0,1},PlotStyle->{Red,Blue,Green}]

We can see that there are three points of intersection: one near 0.25, one near 0.5 and one near 0.75.
In order to estimate these three zeros of f in the interval [0,1] using Newton's method, we begin by defining a function newton, which will be used to compute the successive approximations. This function corresponds to the formula for the Newton iteration mentioned in the Introduction.

newton[x_]:=x-f[x]/f'[x]

If we iterate with this function, then the iteration does not remember all intermediate values (Subscript[x, n]), but instead constantly overwrites the value of x as soon as a better approximate solution has been found (see the line xn=newton[xn] in the code below).

Note that if you insist on using the D operator for the definition of the derivative term in the newton function, then you need to separate the two steps of differentiation and evaluation, i.e., you would have to define newton like this:
newton[x_] := t - f[t]/D[f[t], t] /. t -> x

The following code iterates Newton's method until we have found an x for which f(x) is less than (10^(-10)) in absolute value (see the While[] statement below). The commands PaddedForm and NumberForm are used to format the computed numbers nicely.

xn=0.25;    (* our initial guess *)
Print["(Subscript[x, 0])=", PaddedForm[xn,{12,12}],", f((Subscript[x, 0]))=", NumberForm[f[xn],12]];
k=0;             (* a counter *)
While[Abs[f[xn]]>10^(-10),
xn=newton[xn];
k=k+1;
Print[(Subscript["x", k]),"=", PaddedForm[xn,{12,12}],", f(",(Subscript["x", k]),")=", NumberForm[f[xn],12]];
]

Alternatively, we can use a more cryptic - but much more compact - Mathematica construct based on pure functions and nested lists. You can find more information on theses concepts in the Help. We format the output in the same way as above using PaddedForm.

NestWhileList[newton[#]&,0.25,Abs[f[#]]>10^(-10)&];
PaddedForm[%,{12,12}]

Thus, it appears that the first zero of f in the interval [0,1] has value  x=0.2277581316 when rounded to ten decimal places.
The second zero in the interval [0,1] is approximately x=0.5. 
In fact, this value is exactly 0.5,  since (1/2)=(([Cos(((3π)/4))])^2).
To approximate the final zero of f in [0,1], we make an initial guess using the graph of f created earlier as a reference and apply Newton's method to obtain the successive approximations.          
Taking (Subscript[x, 0])=0.75 we obtain successive estimates similar as before.

xn=0.75;    (* our initial guess *)
Print["(Subscript[x, 0])=", PaddedForm[xn,{12,12}],", f((Subscript[x, 0]))=", NumberForm[f[xn],12]];
k=0;             (* a counter *)
While[Abs[f[xn]]>10^(-10),
xn=newton[xn];
k=k+1;
Print[(Subscript["x", k]),"=", PaddedForm[xn,{12,12}],", f(",(Subscript["x", k]),")=", NumberForm[f[xn],12]];
]

The short nested list version is given by

NestWhileList[newton[#]&,0.75,Abs[f[#]]>10^(-10)&];
PaddedForm[%,{12,12}]

So the final zero rounded to ten decimal places is x=0.7722418684.
In the following example Newton's method is illustrated graphically.

Example 2

Estimate all roots of the third degree polynomial function p(x)=(x^3)-4x-1. 
We begin by graphing the polynomial y=p(x)  in the plane.

p[x_]:=(x^3)-4*x-1
Plot[p[x],{x,-3,3},PlotStyle -> Blue]

Clearly, p has exactly three real zeros. 
Let's use Newton's method, as before, to estimate these roots. Suppose we set (Subscript[x, 0])=1.

As in Example 1, we use a function newton to obtain succesive estimates:

newton[x_]:=x-p[x]/p'[x]

xn=1.0;    (* our initial guess *)
Print["(Subscript[x, 0])=", PaddedForm[xn,{12,12}],", p((Subscript[x, 0]))=", NumberForm[p[xn],12]];
k=0;             (* a counter *)
While[Abs[p[xn]]>10^(-10),
xn=newton[xn];
k=k+1;
Print[(Subscript["x", k]),"=", PaddedForm[xn,{12,12}],", p(",(Subscript["x", k]),")=", NumberForm[p[xn],12]];
]

Finally, we graph the approximations and the tangent lines at each pair ((Subscript[x, n]),p((Subscript[x, n]))) for  n=1,2,. . . ,9, so that we can easily see how (Subscript[x, n+1]) is attained graphically from (Subscript[x, n]) at each stage.

As we saw in the introduction, the idea of the method is as follows: one starts with an initial guess which is reasonably close to the true root, then the function is approximated by its tangent line at that point (which can be computed using the tools of calculus), and one computes the x-intercept of this tangent line (which is easily done with elementary algebra). This x-intercept will typically be a better approximation to the function's root than the original guess, and the method can be iterated.

xn=1.0;
niter=5;
frames=ConstantArray[0,niter+1];
frames[[1]]=Plot[p[x],{x,-3,3},PlotRange->{{-3,3},{-15,15}},PlotStyle->Green];
For[n=2,n≤niter,n++,
xline=Graphics[{Dashed,Line[{{xn,0},{xn,p[xn]}}]}];
tangent=p'[xn]*(x-xn)+p[xn];
tplot=Plot[tangent,{x,-3,3},PlotRange->{{-3,3},{-15,15}},PlotStyle->Red];
frames[[n]]=Show[frames[[n-1]],xline,tplot];
xn=newton[xn];
]
xplot=Graphics[{PointSize[Medium],Blue,Point[{xn,p[xn]}]}];
frames[[niter+1]]=Show[frames[[niter]],xplot];
Manipulate[frames[[n+1]],{n,0,niter,1},FrameLabel->"Newton's Method"]

Exercises

Exercise 1

Let s(x)=((2sin(x))/3)+1.

(a) Show that there exists a number c, called a fixed point of s, in the interval [0,2] for which s(c)=c by plotting a graph of both s(x) and t(x) on [0,2], where t(x) is the identity function (i.e. t(x)=x).

(b) Define f(x)=((2sin(x))/3)+1-x in Mathematica. Then the fixed point c for the function s is the number in [0,2] for which f is zero.
Use Newton's method to approximate the number c accurate to nine decimal places.
Start with the initial approximation (Subscript[x, 0])=2 and display a list of all of the approximations (Subscript[x, 0]),(Subscript[x, 1]),(Subscript[x, 2, ⋯ ,])(Subscript[x, k]) which Mathematica calculates.

Exercise 2

The function t(x)=tan x has a zero at x=π.
Use Newton's method to obtain the value of π to 100 significant digits of accuracy by starting with (Subscript[x, 0])=3.

Exercise 3

The function l(x)=ln (x)-1 has a zero at x=e, Euler's number.
Here, ln(x) denotes the natural logarithmic function.
Use Newton's method to obtain the value of  e to 100 significant digits of accuracy by starting with (Subscript[x, 0])=3.